/**
 * @Author Fizz Pu
 * @Date 2020/9/20 上午11:20
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

 /**
  * 给定一个有 N 个节点的二叉树，每个节点都有一个不同于其他节点且处于 {1, ..., N} 中的值。

通过交换节点的左子节点和右子节点，可以翻转该二叉树中的节点。

考虑从根节点开始的先序遍历报告的 N 值序列。将这一 N 值序列称为树的行程。

（回想一下，节点的先序遍历意味着我们报告当前节点的值，然后先序遍历左子节点，再先序遍历右子节点。）

我们的目标是翻转最少的树中节点，以便树的行程与给定的行程 voyage 相匹配。 

如果可以，则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。

如果不能，则返回列表 [-1]。
  */

import java.util.ArrayList;
import java.util.List;

// 1. 访问根节点
// 2. 左右节点如果可交换, 根节点加到结果集中, 遍历左右左右字树
// 3. 左右节点如果相同, 遍历左右子树
// 4. 如果节点不相等,返回[-1]
// 5. 根节点为空, 返回结果集合
// O(n)

public class Lee971 {
    public List<Integer> res =new ArrayList<>();
    public int index=0;
    public int[] voy;
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        voy=voyage;
       dfs(root);
       return res;
    }

    public void dfs(TreeNode root)
    {
        if(root==null)
        {
            return;
        }
        
        if(root.val!=voy[index])
        {
            res=new ArrayList<Integer>();
            res.add(-1);
            return;
        }
        
        if(root.left!=null&&root.left.val!=voy[index+1])
        {
            index=index+1;
            res.add(root.val);
            dfs(root.right); // 反转左右子树
            dfs(root.left);
        }
        else
        {
            index=index+1;
            dfs(root.left);
            dfs(root.right);
        }
        
    }
}
